/**
 * @ClassName: SimilarStringGroups
 * @Author: Dang Qi
 * @Date: 2021/1/31  9:56
 * @Question.Title: 相似字符串组839
 * @Question.No: 1631
 */
//如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。
//
//例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
//
//总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
//
//给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？
//
// 
//
//示例 1：
//
//输入：strs = ["tars","rats","arts","star"]
//输出：2
//示例 2：
//
//输入：strs = ["omv","ovm"]
//输出：1
// 
//
//提示：
//
//1 <= strs.length <= 100
//1 <= strs[i].length <= 1000
//sum(strs[i].length) <= 2 * 104
//strs[i] 只包含小写字母。
//strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。
// 
//
//备注：
//
//      字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/similar-string-groups
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
package everyday.leetcode.editor.cn;
public class SimilarStringGroups {
    public static void main(String[] args) {
        Solution solution = new SimilarStringGroups().new Solution();
        System.out.println(solution.isSimilar("tars","arts"));

    }
    //leetcode submit region begin(Prohibit modification and deletion)


    class Solution {
        private int N;// 连通分量
        private int[] parent;
        public int numSimilarGroups(String[] strs) {
            parent = new int[strs.length];
            N = strs.length;
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
            for (int i = 0; i < strs.length-1; i++) {
                for (int j = i+1; j < strs.length; j++) {
                    if(i == j || !isSimilar(strs[i],strs[j])) continue;
                    //相似，相当于i和j之间有一条边
                    union(i,j);
                }
            }
            return N;

        }
        public int findRoot(int x){
            while (x != parent[x]){
                x = parent[x];
            }
            return x;
        }
        public void union(int x, int y){
            int x_root = findRoot(x);
            int y_root = findRoot(y);
            if (x_root == y_root) return;
            parent[x_root] = y_root;
            N--;
        }
        public boolean isSimilar(String s1, String s2){
            int len = 0;
            for(int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) != s2.charAt(i) && (++len)>2){
                    return false;
                }
            }
            return len==0||len==2;
        }
    }


    //leetcode submit region end(Prohibit modification and deletion)
}

